import java.util.*;
class Data
{
	int a;
	int b;
}
public class RandomizedQuickSortPi 
{
	public static void exchange(int[] A, int i, int j)
	{
		int temp=0;
		temp = A[i];
		A[i] = A[j];
		A[j] = temp;
	}
	
	public static int random(int p, int r)
	{
		return (int)(p + Math.random()*(r - p + 1));
	}
	
	public static Data randomiedPartitionPi(int[] A, int p, int r)
	{
		int i = p-1,j=p,k = p-1;
		Data d = new Data();
		exchange(A,random(p,r),r);
		for(j=p; j<r; j++)
		{
			if(A[j] < A[r])
			{
				i++;
				exchange(A,i,j);
				k++;
				if(k > i)
					exchange(A,k,j);
			}
			else if(A[j] == A[r])
			{
				k++;
				exchange(A,k,j);
			}
		}
		exchange(A,++k,r);
		d.a = ++i;
		d.b = k;
		return d;
	}

	public static void randomizedQuickSortPi(int[] A, int p, int r)
	{
		if (p < r)
		{
			Data d = randomiedPartitionPi(A, p, r);
			randomizedQuickSortPi(A, p, d.a - 1);
			randomizedQuickSortPi(A, d.b + 1, r);
		}
	}
	
	public static void main(String[] args)
	{
		int[] A = {0, 2, 7, 7, 6, 8, 2, 8, 8, 3, 4};
		System.out.println(Arrays.toString(A));
		randomizedQuickSortPi(A, 1, A.length-1);
		System.out.println(Arrays.toString(A));
	}
}
